Sao Hỏa có hai vệ tinh tự nhiên tương đối nhỏ, Phobos và Deimos, chúng quay quanh trên những quỹ đạo khá gần hành tinh. Lý thuyết về tiểu hành tinh bị hành tinh đỏ bắt giữ đã thu hút sự quan tâm từ lâu nhưng nguồn gốc của nó vẫn còn nhiều bí ẩn.[117] Nhà thiên văn học Asaph Hall đã phát hiện ra 2 vệ tinh này vào năm 1877, và ông đặt tên chúng theo tên các nhân vật trong thần thoại Hy Lạp là Phobos (đau đớn/sợ hãi) và Deimos (kinh hoàng/khiếp sợ), hai người con cùng tham gia những trận đánh của vị thần chiến tranh Ares. Ares trong thần thoại La Mã tên là Mars (mà người La Mã dùng tên của vị thần đó đặt tên cho Sao Hỏa).[118][119]

Nhìn từ bề mặt Hỏa Tinh, chuyển động của Phobos và Deimos hiện lên rất khác lạ so với chuyển động của Mặt Trăng. Phobos mọc lên ở phía tây, lặn ở phía đông, và lại mọc lên chỉ sau 11 giờ. Deimos nằm ngay bên ngoài quỹ đạo khóa thủy triều—tại đó chu kỳ quỹ đạo bằng với chu kỳ tự quay của hành tinh—nó mọc lên ở phía đông nhưng rất chậm. Mặc dù chu kỳ quỹ đạo của nó bằng 30 giờ, nó phải mất 2,7 ngày để lặn ở phía tây khi nó chậm dần đi về phía sau sự quay của Sao Hỏa, và sau đó phải khá lâu nó mới mọc trở lại.[120]

Bởi vì quỹ đạo của Phobos nằm bên trong quỹ đạo đồng bộ, lực thủy triều từ Hỏa Tinh đang dần dần hút vệ tinh này về phía nó. Trong khoảng 50 triệu năm nữa vệ tinh này sẽ đâm xuống bề mặt Sao Hỏa hoặc bị phá tan thành một cái vành bụi quay quanh hành tinh.[120]

Nguồn gốc của hai vệ tinh này vẫn chưa được hiểu đầy đủ. Đặc tính suất phản chiếu hình học thấp và thành phần cấu tạo bằng "thiên thạch hạt chứa than" (carbonaceous chondrite) giống với tính chất của các tiểu hành tinh là một trong những bằng chứng ủng hộ lý thuyết tiểu hành tinh bị bắt. Quỹ đạo không ổn định của Phobos dường như là một chứng cứ khác cho thấy nó bị bắt trong thời gian khá gần ngày nay. Tuy vậy, cả hai vệ tinh có quỹ đạo tròn, mặt phẳng quỹ đạo rất gần với mặt phẳng xích đạo hành tinh, lại là một điều không thông thường cho các vật thể bị bắt và như thế đòi hỏi quá trình động lực bắt giữ 2 vệ tinh này rất phức tạp. Sự bồi tụ trong buổi đầu lịch sử hình thành Sao Hỏa cũng là một khả năng khác nhưng lý thuyết này lại không giải thích được thành phần cấu tạo của 2 vệ tinh giống với các tiểu hành tinh hơn là giống với thành phần của Hỏa Tinh.

Một khả năng khác đó là sự tham gia của một vật thể thứ ba hoặc một kiểu va chạm gây nhiễu loạn.[121] Những dữ liệu gần đây cho thấy khả năng vệ tinh Phobos có cấu trúc bên trong khá rỗng[122] và các nhà khoa học đề xuất thành phần chính của nó là khoáng phyllosilicat và những loại khoáng vật khác đã có trên Sao Hỏa,[123] và họ chỉ ra trực tiếp rằng nguồn gốc của Phobos là từ những vật liệu bắn ra từ một thiên thể va chạm với Sao Hỏa và sau đó tích tụ lại trên quỹ đạo quanh hành tinh này,[124] tương tự như lý thuyết giải thích cho nguồn gốc Mặt Trăng. Trong khi phổ VNIR của các vệ tinh Sao Hỏa giống với phổ của các tiểu hành tinh trong vành đai tiểu hành tinh, thì phổ hồng ngoại nhiệt (thermal infrared) của Phobos lại không hoàn toàn tương thích với phổ của bất kỳ lớp khoáng vật chondrit.[123]